package com.icbc.DataStructuresAndAlgorithms;

import java.util.*;

/**
 * 图的创建及存储形式
 */
public class GraphDomo {
	public static void main(String[] args) {
		//创建初始数据
		Map<String, Integer> map = new HashMap<String, Integer>(){
			{
				put("A",0);
				put("B",1);
				put("C",2);
				put("D",3);
				put("E",4);
			}
		};
		//初始化图
		Graph graph = new Graph(5);
		//添加顶点
		map.forEach((a,b) -> graph.insertVertex(a));
		//添加边
		graph.insertEdges(map.get("A"),map.get("E"),1);
		graph.insertEdges(map.get("A"),map.get("C"),1);
		graph.insertEdges(map.get("C"),map.get("D"),1);
		//graph.insertEdges(map.get("B"),map.get("E"),1);
		graph.insertEdges(map.get("B"),map.get("D"),1);
		//遍历
		graph.dfs();
		System.out.println("===================");
		graph.bfs();
		
	}
}

class Graph{
	//首先图的顶点值需要使用一个ArrayList来存储
	private ArrayList<String> vertexList;
	//图的边使用二维数组来储存
	private int[][] edges;
	//定义一个属性存储图的边的数量
	private int numOfEdges;
	public Graph(int n){
		vertexList = new ArrayList<>(n);
		edges = new int[n][n];
	}
	//添加顶点值
	public void insertVertex(String value){
		vertexList.add(value);
	}
	
	//添加边,row是行索引,col是列索引,weight是边的权值
	public void insertEdges(int row,int col,int weight){
		if (row + 1 > vertexList.size() || col + 1 > vertexList.size()){
			System.out.println("超出边界!!");
		}else{
			edges[row][col] = weight;
			edges[col][row] = weight;
			numOfEdges++;
		}
	}
	
	//遍历
	public void list(){
		Arrays.stream(edges).forEach(a -> System.out.println(Arrays.toString(a)));
	}
	
	/**
	 * 得到传入的下标为index节点的第一个临近节点下标w
	 * @param index 传入的节点下标
	 * @return	返回的传入节点第一个临近节点的下标
	 */
	public int getFirstNeighbor(int index){
		for (int i = 0; i < vertexList.size(); i++) {
			if (edges[index][i] > 0){
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 根据前一个临接节点的下标来获取下一个临接节点下标
	 * @param v
	 * @param w
	 * @return
	 */
	public int getNextNeighbor(int v,int w){
		for (int i = w + 1; i < vertexList.size(); i++) {
			if (edges[v][i] > 0){
				return i;
			}
		}
		return -1;
	}
	
	//深度遍历(DFS),深度遍历一个节点
	private void dfs(boolean[] isVisible,int i){
		//打印节点
		System.out.println(vertexList.get(i));
		//将该节点的读取状态改为已读取
		isVisible[i] = true;
		//查找节点i的第一个临近节点
		int w = getFirstNeighbor(i);
		//w不为-1时表示找到了下一个临接节点
		while (w != -1){
			/*
			 * 验证w是否已经被读取过
			 * 没有读取过递归
			 * 读取过就获取该节点也就是i的下一个临接节点
			 */
			if (!isVisible[w]){
				dfs(isVisible,w);
			}
			//如果w节点已经访问过了,就过去i节点的w之后的下一个临接节点
			w = getNextNeighbor(i,w);
		}
	}
	
	//深度遍历(DFS)主方法
	public void dfs(){
		boolean[] isVisible = new boolean[vertexList.size()];
		for (int i = 0; i < vertexList.size(); i++) {
			if (!isVisible[i]){
				dfs(isVisible,i);
			}
		}
	}
	
	//广度优先遍历(BFS),广度遍历一个节点
	private void bfs(boolean[] isVisible,int i){
		int u;//队列头节点对应的下标
		int w;//头节点的临接节点下标
		//队列,记录节点访问的顺序
		LinkedList<Integer> queue = new LinkedList<>();
		//打印当前节点
		System.out.println(vertexList.get(i));
		//将当前节点设置为已访问
		isVisible[i] = true;
		//加入队列
		queue.addLast(i);
		//从队列中取出数据进行广度遍历
		while (!queue.isEmpty()){
			//取出队列的头节点
			u = queue.removeFirst();
			//得到第一个临接点的下标
			w = getFirstNeighbor(u);
			while (w != -1){//找到
				//是否访问过
				if (!isVisible[w]){
					System.out.println(vertexList.get(w));
					isVisible[w] = true;
					queue.addLast(w);
				}
				//如果没有访问过,以u为起始,查找w后面的临接节点
				w = getNextNeighbor(u, w);
			}
		}
	}
	//广度优先遍历(BFS)主方法
	public void bfs(){
		boolean[] isVisible = new boolean[vertexList.size()];
		for (int i = 0; i < vertexList.size(); i++) {
			if (!isVisible[i]){
				bfs(isVisible,i);
			}
		}
	}
}
